import math

# 商品体积数据，单位是立方米  转为立方分米
volume_arr = [
    1.180, 8.92088, 4.58139, 5.29266, 1.23892, 3.93005, 7.53638, 6.92084, 3.89288, 4.67208, 0.37816, 0.7633, 1.49049, 0.2945, 3.63577, 4.53125, 6.86774, 7.03136,
    8.32038, 3.28645, 0.92165, 6.0227, 6.67724, 2.25087, 6.36347, 0.91234, 0.4131, 6.03253, 2.10624, 0.94981, 5.49145, 1.84597, 1.64853, 4.24115, 2.70332, 3.73644,
    5.50686, 4.85712, 5.72609, 3.07901, 5.43169, 7.88526, 2.37452, 2.87198, 6.30832, 3.03864, 3.19001, 3.50305, 0.28338, 9.95386, 3.94953, 6.72467, 3.82848, 3.03825,
    6.27153, 9.97295, 6.87071, 8.19529, 8.23215, 0.75555, 3.89223, 2.5766, 1.29116, 3.21259, 1.45661, 7.13919, 9.66758, 5.29364, 0.59208, 1.06844, 6.91517, 6.27877,
    6.27153, 9.97295, 6.87071, 8.19529, 8.23215, 0.75555, 3.89223, 2.5766, 1.29116, 3.21259, 1.45661, 7.13919, 9.66758, 5.29364, 0.59208, 1.06844, 6.91517, 6.27877,
    1.50904, 6.50522, 1.77932, 6.30585, 1.19917, 4.87037, 1.07854, 7.28688, 3.50365, 2.16646, 0.5104, 1.01293, 4.91249, 6.23181, 2.64389, 3.06228, 5.61209, 3.58101,
    1.50904, 6.50522, 1.77932, 6.30585, 1.19917, 4.87037, 1.07854, 7.28688, 3.50365, 2.16646, 0.5104, 1.01293, 4.91249, 6.23181, 2.64389, 3.06228, 5.61209, 3.58101,

]
# 每辆车的体积，单位是立方米  转为立方分米
max_vol = 40 * 1000

# 对小数数组进行整数化处理，返回一个int类型的数组
def translate(volume_arr):
    new_volume_arr = []
    for vol in volume_arr:
        vol_num = int(math.ceil(vol * 1000))
        new_volume_arr.append(vol_num)
    return new_volume_arr

# 统计每个体积数据出现的次数，同时获取到去重之后的体积数据
def get_vol_arr(volume_arr):
    volume_count = {}
    for vol in volume_arr:
        if vol in volume_count:
            volume_count[vol] += 1
        else:
            volume_count[vol] = 1
    new_volume_arr = list(volume_count.keys())
    nums_arr = list(volume_count.values())
    return [new_volume_arr, nums_arr]

# 判断货物是否被全部装完
def is_complete(nums_arr):
    return sum(nums_arr) == 0

# 求取一辆车最大使用空间
def get_max_volume_multi(volume_arr, capacity, nums_arr):
    num = 0
    while not is_complete(nums_arr):
        num += 1
        dp = [[0 for _ in range(capacity + 1)] for _ in range(len(volume_arr) + 1)]
        for i in range(1, len(volume_arr) + 1):
            for j in range(1, capacity + 1):
                for k in range(min(nums_arr[i - 1] + 1, j // volume_arr[i - 1] + 1)):
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * volume_arr[i - 1]] + k * volume_arr[i - 1])
        print(f"第{num}辆车，最大组合体积为{dp[len(volume_arr)][capacity]}")
        volume_arr, nums_arr = print_goods_info(dp, volume_arr, capacity, nums_arr)

# 输出选择的商品组合信息
def print_goods_info(dp, volume_arr, capacity, nums_arr):
    i = len(volume_arr)
    j = capacity
    while i > 0 and j > 0:
        for k in range(1, nums_arr[i - 1] + 1):
            if j - k * volume_arr[i - 1] >= 0 and dp[i][j] == dp[i - 1][j - k * volume_arr[i - 1]] + k * volume_arr[i - 1]:
                print(f"{volume_arr[i - 1]}选择了{k}件；")
                j = j - k * volume_arr[i - 1]
                nums_arr[i - 1] -= k
                break
        i -= 1
    new_volume_arr = []
    new_nums_arr = []
    for i in range(len(nums_arr)):
        if nums_arr[i] != 0:
            new_volume_arr.append(volume_arr[i])
            new_nums_arr.append(nums_arr[i])
    return new_volume_arr, new_nums_arr

if __name__ == "__main__":
    arr = translate(volume_arr)
    volume_arr, nums_arr = get_vol_arr(arr)
    get_max_volume_multi(volume_arr, max_vol, nums_arr)